following content has been provided by the University of Erlangen-Nürnberg.

Yesterday we talked about gameplaying or, as we say in a slightly more scientific way

adversarial search. You do search-based problem-solving but

but there is an adversary in the room.

Last week we learned about minimax search,

and here we actually improve on this very basic idea

of minimax search.

What comes out is alpha beta search.

The idea is relatively simple.

The idea is that we can actually snip off

certain areas of the search space,

and it turns out that we can snip off

in the overall effect,

an exponential part of the exponential search space.

What stays over is still exponential,

but in D over two instead of in D.

And D is the critical depth of the solution

is the critical factor.

So that actually gives us double the look ahead.

The idea was that if Max knows

that he can always achieve an N

because min after looking at the min subtree here

cannot force less than N,

then further down the tree,

when you already see I have an M here,

which is smaller than N,

I do not have to look at this.

Because we're again under min,

and we know that here min can't force less than N,

so we don't have to look at the small values here.

Anything under this max tree here.

Okay? So the idea here is that we can save a little bit here,

and if we are in a good situation,

we can essentially make every second layer of the tree to be choiceless,

which gives us this depth over two things.

So we looked at the examples in detail,

and the idea of alpha pruning is that next to the value,

which you always compute,

you also hold on to the so-called alpha value,

which is really something that actually is going to be transferred into the other branches.

Here the alpha value of three is transferred,

even though the value that looks below is completely indetermined,

and therefore plus on infinity here.

Once you see something that's smaller than three,

you can get rid of all the others.

So we looked at the algorithm,

and I fixed the typo and essentially run the algorithm with the pruning both for max as well as for min.

We get a nice speed up here.

At least one of these things here is choiceless.

Choicelessness we always get if we have ordered the nodes correctly.